前言

先來個之前寫過覺得還算值得練習的DP題目~152. Maximum Product Subarray，之前一時看了沒有頭緒該怎麼寫，把經過過程寫下來~

解法

本來看到題目轉過很多想法~ 想說都是整數，那只要結果是正的&不是0，都是越長越好，所以可能可以預設全部相乘，這個當暫存的最大值(greedy魂上身)：如果是0或是負的再去檢查；是負的就從兩邊找到第一個負的看哪邊乘起來比較大就不要，變回原本問題，更新最大值之後繼續找，就是從兩邊去削減，直到變成正的或是整條都沒了；是0的就看從哪邊去掉0比較不傷(直接比兩邊結果)，但想不出來怎麼實現，所以看了別人的想法當提示，我現在也來當那個別人，說不定看到這個想法就可以解出來了~

• 解法一
  • 使用DP內存兩個值，紀錄包含該位置值的最大乘積跟最小乘積，然後每次就考慮最大乘積跟最小乘積的更新max(前一個*該個,該個)、min(前一個*該個,該個)，來進行更新。為什麼需要存最小值?因為如果下一個是負數的話就需要，大小值會整個反過來，就不用特別考慮什麼最大值、最小值、0要怎麼取了反正一定是3者之一，直覺易懂，程式碼如下：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // DP way
        vector<int> maxProd(nums.size());
        vector<int> minProd(nums.size());
        
        // initial the first one
        maxProd[0] = nums[0];
        minProd[0] = nums[0];
        int ans=nums[0];
        // iterate to compute from the previous one
        for(int i=1; i<nums.size(); ++i){
            maxProd[i] = max({maxProd[i-1]*nums[i],minProd[i-1]*nums[i],nums[i]});
            minProd[i] = min({maxProd[i-1]*nums[i],minProd[i-1]*nums[i],nums[i]});
            ans = max(ans, maxProd[i]);
        }
        return ans;
    }
};

另外也有看到leetcode討論區神人的簡化寫法，整理如下：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0], mx = res, mn = res;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < 0) swap(mx, mn);
            mx = max(nums[i], mx * nums[i]);
            mn = min(nums[i], mn * nums[i]);
            res = max(res, mx);
        }
        return res;
    }
};

• 解法二
  • 另外一個酷解法(應該算是greedy)，直接用兩次for迴圈，用類似累加的方式來greedy解。其實它的概念很簡單，就是maxima array不是靠左就是靠右，不會有在中間的情形(因為乘越多越好，要捨棄的情形只有是負數或是0的情形，而負數的話如果兩邊都要捨那應該兩邊都包含進去)，0的情形另外考慮：如果有0的那段砍掉，就變成原問題，程式碼如下：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // greedy, the subarray would either start from left or right
        // record the current maxima value
        int ans=-10;
        // record the current product
        int prod=1;
        // start from right
        for(int i=0; i<nums.size();++i){
            prod*=nums[i];
            ans=max(ans, prod);
            // if 0 appears, regarded as subproblem starting from the next element
            prod = nums[i]==0?1:prod;
        }
        // start from left
        prod = 1;
        for(int i=nums.size()-1; i>=0;--i){
            prod*=nums[i];
            ans=max(ans, prod);
            // if 0 appears, regarded as subproblem starting from the next element
            prod = nums[i]==0?1:prod;
        }
        return ans;
    }
};

另外一樣也有討論區的大神把兩個簡化寫在一起~

int maxProduct(vector<int> A) {
        int n = A.size(), res = A[0], l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            l =  (l ? l : 1) * A[i];
            r =  (r ? r : 1) * A[n - 1 - i];
            res = max(res, max(l, r));
        }
        return res;
    }

結語

今日挑戰的題目乍看單純但其實蠻有趣的(也蠻麻煩XD)改天把他補上~